﻿/**
 * @file std_rbtree.c
 * Copyright (c) 2019 Gaaagaa. All rights reserved.
 * 
 * @author  : Gaaagaa
 * @date    : 2019-09-09
 * @version : 1.0.0.0
 * @brief   : 使用 C API 的接口形式实现 红黑树 容器。
 */

/**
 * The MIT License (MIT)
 * Copyright (c) Gaaagaa. All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "std_rbtree.h"
#include "std_debug.h"
#include "std_rbtree.inl"

////////////////////////////////////////////////////////////////////////////////

#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-function"
#endif // __GNUC__

////////////////////////////////////////////////////////////////////////////////

//====================================================================

// 
// xstd_rbtree_t 的内部操作接口
// 

/**********************************************************/
/**
 * @brief 申请节点对象缓存。
 */
static xrbt_iter_t rbtree_node_malloc(xrbt_this_t xrbt_this)
{
#if XRBT_ELEM_SEPARATED

    xrbt_iter_t xiter_node = 
        (xrbt_iter_t)XRBT_MALLOC(xrbt_this, sizeof(xrbt_node_t));
    XASSERT(XRBT_NULL != xiter_node);

    XRBT_ITER_ELEM(xiter_node) = 
        (xrbt_elem_t)XRBT_MALLOC(xrbt_this, XRBT_ESIZE(xrbt_this));
    XASSERT(XRBT_NULL != XRBT_ITER_ELEM(xiter_node));

#else // !XRBT_ELEM_SEPARATED

    xrbt_iter_t xiter_node = 
        (xrbt_iter_t)XRBT_MALLOC(
            xrbt_this, sizeof(xrbt_node_t) + XRBT_ESIZE(xrbt_this));
    XASSERT(XRBT_NULL != xiter_node);

#endif // XRBT_ELEM_SEPARATED

#if (XSTD_DEBUG_LEVEL >= XSTD_DEBUG_LOWER)
    xiter_node->xrbt_owner = xrbt_this;
#endif // XSTD_DEBUG_LOWER

    return xiter_node;
}

/**********************************************************/
/**
 * @brief 销毁节点对象。
 */
static xrbt_void_t rbtree_node_dealloc(
                        xrbt_this_t xrbt_this,
                        xrbt_iter_t xiter_node)
{
    XASSERT(XRBT_ITER_NOTNIL(xiter_node));

    XRBT_ALDEST(xrbt_this, XRBT_ITER_ELEM(xiter_node));

#if XRBT_ELEM_SEPARATED
    XRBT_DEALLOC(xrbt_this, XRBT_ITER_ELEM(xiter_node));
#endif // XRBT_ELEM_SEPARATED

    XRBT_DEALLOC(xrbt_this, xiter_node);
}

/**********************************************************/
/**
 * @brief 返回最左侧的节点。
 */
static inline xrbt_iter_t rbtree_far_left(xrbt_iter_t xiter_node)
{
    while (XRBT_ITER_NOTNIL(xiter_node->xiter_left))
    {
        xiter_node = xiter_node->xiter_left;
    }

    return xiter_node;
}

/**********************************************************/
/**
 * @brief 返回最右侧的节点。
 */
static inline xrbt_iter_t rbtree_far_right(xrbt_iter_t xiter_node)
{
    while (XRBT_ITER_NOTNIL(xiter_node->xiter_right))
    {
        xiter_node = xiter_node->xiter_right;
    }

    return xiter_node;
}

/**********************************************************/
/**
 * @brief 使用递归方式释放分支上的所有节点资源。
 */
static xrbt_void_t rbtree_clear_branch(
                        xrbt_this_t xrbt_this,
                        xrbt_iter_t xiter_branch_root)
{
#if 1
    xrbt_iter_t xiter_node = xiter_branch_root;

    while (XRBT_ITER_NOTNIL(xiter_node))
    {
        if (XRBT_ITER_NOTNIL(xiter_node->xiter_right))
        {
            rbtree_clear_branch(xrbt_this, xiter_node->xiter_right);
        }

        xiter_branch_root = xiter_node->xiter_left;
        rbtree_node_dealloc(xrbt_this, xiter_node);
        xiter_node = xiter_branch_root;
    }
#else
    if (XRBT_ITER_ISNIL(xiter_branch_root))
        return;

    if (XRBT_ITER_NOTNIL(xiter_branch_root->xiter_left))
        rbtree_clear_branch(xrbt_this, xiter_branch_root->xiter_left);

    if (XRBT_ITER_NOTNIL(xiter_branch_root->xiter_right))
        rbtree_clear_branch(xrbt_this, xiter_branch_root->xiter_right);

    rbtree_node_dealloc(xrbt_this, xiter_branch_root);
#endif
}

/**********************************************************/
/**
 * @brief 查找父级后继节点（即查找 “节点元素值大于该节点” 的 “最小父级节点” ）。
 */
static inline xrbt_iter_t rbtree_successor_parent(xrbt_iter_t xiter_node)
{
    while (XRBT_ITER_NOTNIL(xiter_node->xiter_parent) &&
           (xiter_node->xiter_parent->xiter_right == xiter_node))
    {
        xiter_node = xiter_node->xiter_parent;
    }

    return xiter_node->xiter_parent;
}

/**********************************************************/
/**
 * @brief 查找父级前驱节点（即查找 “节点元素值小于该节点” 的 “最大父级节点” ）。
 */
static inline xrbt_iter_t rbtree_precursor_parent(xrbt_iter_t xiter_node)
{
    while (XRBT_ITER_NOTNIL(xiter_node->xiter_parent) &&
           (xiter_node->xiter_parent->xiter_left == xiter_node))
    {
        xiter_node = xiter_node->xiter_parent;
    }

    return xiter_node->xiter_parent;
}

/**********************************************************/
/**
 * @brief 查找后继节点（即查找 “节点元素值大于该节点” 的 “最小节点” ）。
 */
static inline xrbt_iter_t rbtree_successor(xrbt_iter_t xiter_node)
{
    if (XRBT_ITER_NOTNIL(xiter_node->xiter_right))
    {
        return rbtree_far_left(xiter_node->xiter_right);
    }

    return rbtree_successor_parent(xiter_node);
}

/**********************************************************/
/**
 * @brief 查找前驱节点（即查找 “节点元素值小于该节点” 的 “最大节点” ）。
 */
static inline xrbt_iter_t rbtree_precursor(xrbt_iter_t xiter_node)
{
    if (XRBT_ITER_NOTNIL(xiter_node->xiter_left))
    {
        return rbtree_far_right(xiter_node->xiter_left);
    }

    return rbtree_precursor_parent(xiter_node);
}

/**********************************************************/
/**
 * @brief 对节点进行左旋转操作。
 */
static xrbt_void_t rbtree_left_rotate(
                        xrbt_this_t xrbt_this,
                        xrbt_iter_t xiter_node)
{
    xrbt_iter_t xiter_swap = xiter_node->xiter_right;

    xiter_node->xiter_right = xiter_swap->xiter_left;
    if (XRBT_ITER_NOTNIL(xiter_swap->xiter_left))
    {
        xiter_swap->xiter_left->xiter_parent = xiter_node;
    }

    xiter_swap->xiter_parent = xiter_node->xiter_parent;
    if (XRBT_ITER_ISNIL(xiter_node->xiter_parent))
    {
        xrbt_this->xiter_root = xiter_swap;
    }
    else if (xiter_node == xiter_node->xiter_parent->xiter_left)
    {
        xiter_node->xiter_parent->xiter_left = xiter_swap;
    }
    else
    {
        xiter_node->xiter_parent->xiter_right = xiter_swap;
    }

    xiter_swap->xiter_left   = xiter_node;
    xiter_node->xiter_parent = xiter_swap;
}

/**********************************************************/
/**
 * @brief 对节点进行右旋转操作。
 */
static xrbt_void_t rbtree_right_rotate(
                        xrbt_this_t xrbt_this,
                        xrbt_iter_t xiter_node)
{
    xrbt_iter_t xiter_swap = xiter_node->xiter_left;

    xiter_node->xiter_left = xiter_swap->xiter_right;
    if (XRBT_ITER_NOTNIL(xiter_swap->xiter_right))
    {
        xiter_swap->xiter_right->xiter_parent = xiter_node;
    }

    xiter_swap->xiter_parent = xiter_node->xiter_parent;
    if (XRBT_ITER_ISNIL(xiter_node->xiter_parent))
    {
        xrbt_this->xiter_root = xiter_swap;
    }
    else if (xiter_node == xiter_node->xiter_parent->xiter_right)
    {
        xiter_node->xiter_parent->xiter_right = xiter_swap;
    }
    else
    {
        xiter_node->xiter_parent->xiter_left = xiter_swap;
    }

    xiter_swap->xiter_right  = xiter_node;
    xiter_node->xiter_parent = xiter_swap;
}

/**********************************************************/
/**
 * @brief 将节点停靠到 xstd_rbtree_t 时，对 xstd_rbtree_t 进行修正。
 */
static xrbt_void_t rbtree_dock_fixup(
                        xrbt_this_t xrbt_this,
                        xrbt_iter_t xiter_where)
{
    xrbt_iter_t xiter_uncle = XRBT_ITER_NIL(xrbt_this);

    // xiter_where ---> XCLR_RED
    while (XCLR_RED == xiter_where->xiter_parent->xst_color)
    {
        if (xiter_where->xiter_parent == xiter_where->xiter_parent->xiter_parent->xiter_left)
        {
            xiter_uncle = xiter_where->xiter_parent->xiter_parent->xiter_right;
            if (XCLR_RED == xiter_uncle->xst_color)
            {
                xiter_where->xiter_parent->xst_color = XCLR_BLACK;
                xiter_uncle->xst_color = XCLR_BLACK;
                xiter_where->xiter_parent->xiter_parent->xst_color = XCLR_RED;

                // xiter_where --> XCLR_RED
                xiter_where = xiter_where->xiter_parent->xiter_parent;
            }
            else
            {
                if (xiter_where == xiter_where->xiter_parent->xiter_right)
                {
                    xiter_where = xiter_where->xiter_parent;
                    rbtree_left_rotate(xrbt_this, xiter_where);
                }

                xiter_where->xiter_parent->xst_color = XCLR_BLACK;
                xiter_where->xiter_parent->xiter_parent->xst_color = XCLR_RED;
                rbtree_right_rotate(xrbt_this, xiter_where->xiter_parent->xiter_parent);
            }
        }
        else
        {
            xiter_uncle = xiter_where->xiter_parent->xiter_parent->xiter_left;
            if (XCLR_RED == xiter_uncle->xst_color)
            {
                xiter_where->xiter_parent->xst_color = XCLR_BLACK;
                xiter_uncle->xst_color = XCLR_BLACK;
                xiter_where->xiter_parent->xiter_parent->xst_color = XCLR_RED;

                // xiter_where --> XCLR_RED
                xiter_where = xiter_where->xiter_parent->xiter_parent;
            }
            else
            {
                if (xiter_where == xiter_where->xiter_parent->xiter_left)
                {
                    xiter_where = xiter_where->xiter_parent;
                    rbtree_right_rotate(xrbt_this, xiter_where);
                }

                xiter_where->xiter_parent->xst_color = XCLR_BLACK;
                xiter_where->xiter_parent->xiter_parent->xst_color = XCLR_RED;
                rbtree_left_rotate(xrbt_this, xiter_where->xiter_parent->xiter_parent);
            }
        }
    }

    xrbt_this->xiter_root->xst_color = XCLR_BLACK;
}

/**********************************************************/
/**
 * @brief 
 * 将节点从 xstd_rbtree_t 中分离出来（移除）时，
 * 对 xstd_rbtree_t 进行修正。
 */
static xrbt_void_t rbtree_undock_fixup(
                        xrbt_this_t xrbt_this,
                        xrbt_iter_t xiter_where,
                        xrbt_iter_t xiter_parent)
{
    xrbt_iter_t xiter_sibling = XRBT_ITER_NIL(xrbt_this);

    for (; (xiter_where != xrbt_this->xiter_root) &&
           (XCLR_BLACK == xiter_where->xst_color);
         xiter_parent = xiter_where->xiter_parent)
    {
        if (xiter_where == xiter_parent->xiter_left)
        {
            xiter_sibling = xiter_parent->xiter_right;
            if (XCLR_RED == xiter_sibling->xst_color)
            {
                xiter_sibling->xst_color = XCLR_BLACK;
                xiter_parent->xst_color = XCLR_RED;
                rbtree_left_rotate(xrbt_this, xiter_parent);
                xiter_sibling = xiter_parent->xiter_right;
            }

            if (XRBT_ITER_ISNIL(xiter_sibling))
            {
                xiter_where = xiter_parent;
            }
            else if ((XCLR_BLACK == xiter_sibling->xiter_left->xst_color) &&
                     (XCLR_BLACK == xiter_sibling->xiter_right->xst_color))
            {
                xiter_sibling->xst_color = XCLR_RED;
                xiter_where = xiter_parent;
            }
            else
            {
                if (XCLR_BLACK == xiter_sibling->xiter_right->xst_color)
                {
                    xiter_sibling->xiter_left->xst_color = XCLR_BLACK;
                    xiter_sibling->xst_color = XCLR_RED;
                    rbtree_right_rotate(xrbt_this, xiter_sibling);
                    xiter_sibling = xiter_parent->xiter_right;
                }

                xiter_sibling->xst_color = xiter_parent->xst_color;
                xiter_parent->xst_color = XCLR_BLACK;
                xiter_sibling->xiter_right->xst_color = XCLR_BLACK;
                rbtree_left_rotate(xrbt_this, xiter_parent);
                break;	// tree now recolored/rebalanced
            }
        }
        else
        {
            xiter_sibling = xiter_parent->xiter_left;
            if (XCLR_RED == xiter_sibling->xst_color)
            {
                xiter_sibling->xst_color = XCLR_BLACK;
                xiter_parent->xst_color = XCLR_RED;
                rbtree_right_rotate(xrbt_this, xiter_parent);
                xiter_sibling = xiter_parent->xiter_left;
            }

            if (XRBT_ITER_ISNIL(xiter_sibling))
            {
                xiter_where = xiter_parent;
            }
            else if ((XCLR_BLACK == xiter_sibling->xiter_right->xst_color) &&
                     (XCLR_BLACK == xiter_sibling->xiter_left->xst_color))
            {
                xiter_sibling->xst_color = XCLR_RED;
                xiter_where = xiter_parent;
            }
            else
            {
                if (XCLR_BLACK == xiter_sibling->xiter_left->xst_color)
                {
                    xiter_sibling->xiter_right->xst_color = XCLR_BLACK;
                    xiter_sibling->xst_color = XCLR_RED;
                    rbtree_left_rotate(xrbt_this, xiter_sibling);
                    xiter_sibling = xiter_parent->xiter_left;
                }

                xiter_sibling->xst_color = xiter_parent->xst_color;
                xiter_parent->xst_color = XCLR_BLACK;
                xiter_sibling->xiter_left->xst_color = XCLR_BLACK;
                rbtree_right_rotate(xrbt_this, xiter_parent);
                break;	// tree now recolored/rebalanced
            }
        }
    }

    xiter_where->xst_color = XCLR_BLACK;
}

/**********************************************************/
/**
 * @brief 在指定的子树上，获取节点元素值可停靠的位置。
 * 
 * @param [in ] xrbt_this  : xstd_rbtree_t 对象。
 * @param [in ] xrbt_elem  : 节点元素值。
 * @param [in ] xiter_root : 指定子树的根节点位置。
 * @param [out] xrbt_dpos  : 返回的停靠方式（参看 xrbt_dpos_t 枚举值）。
 * 
 * @return xrbt_iter_t : 可停靠节点位置的迭代器。
 * 若返回的 xrbt_dpos == XDPOS_NONE 时，
 * 迭代器对应的 节点元素值 与 xrbt_elem 相等。
 */
static xrbt_iter_t rbtree_dpos_root(
                        xrbt_this_t xrbt_this,
                        xrbt_elem_t xrbt_elem,
                        xrbt_iter_t xiter_root,
                        xrbt_dpos_t * xrbt_dpos)
{
    xrbt_iter_t xiter_node = XRBT_ITER_NIL(xrbt_this);
    xrbt_iter_t xiter_trav = XRBT_ITER_NIL(xrbt_this);

    *xrbt_dpos = XDPOS_RIGHT;

    while (XRBT_ITER_NOTNIL(xiter_root))
    {
        xiter_node = xiter_root;
        if (XRBT_ELEM_LT(xrbt_this, XRBT_ITER_ELEM(xiter_root), xrbt_elem))
        {
            *xrbt_dpos = XDPOS_RIGHT;
            xiter_root = xiter_root->xiter_right;
        }
        else
        {
            *xrbt_dpos = XDPOS_LEFT;
            xiter_trav = xiter_root;
            xiter_root = xiter_root->xiter_left;
        }
    }

    if (XRBT_ITER_NOTNIL(xiter_trav) &&
        !XRBT_ELEM_LT(xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_trav)))
    {
        *xrbt_dpos = XDPOS_NONE;
        return xiter_trav;
    }

    return xiter_node;
}

/**********************************************************/
/**
 * @brief 
 * 协助 @see rbtree_dpos_hint() 接口，实现树结构体的左侧方向检索操作。
 */
static xrbt_iter_t rbtree_dpos_left(
                        xrbt_this_t xrbt_this,
                        xrbt_elem_t xrbt_elem,
                        xrbt_iter_t xiter_hint,
                        xrbt_dpos_t * xrbt_dpos)
{
    xrbt_iter_t xiter_trav = xiter_hint;
#if 1
    //======================================
    // the precursor of parent

    for (;;)
    {
        xiter_trav = rbtree_precursor_parent(xiter_hint);
        if (XRBT_ITER_ISNIL(xiter_trav))
        {
            break;
        }

        // xrbt_elem < XRBT_ITER_ELEM(xiter_trav)
        if (XRBT_ELEM_LT(xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_trav)))
        {
            xiter_hint = xiter_trav;
        }
        else
        {
            // xrbt_elem > XRBT_ITER_ELEM(xiter_trav)
            if (XRBT_ELEM_LT(xrbt_this, XRBT_ITER_ELEM(xiter_trav), xrbt_elem))
            {
                break;
            }

            // xrbt_elem == XRBT_ITER_ELEM(xiter_trav)
            *xrbt_dpos = XDPOS_NONE;
            return xiter_trav;
        }
    }

    //======================================
    // the sub branch of left

    for (xiter_trav = xiter_hint; XRBT_ITER_NOTNIL(xiter_trav->xiter_left); )
    {
        // xrbt_elem < XRBT_ITER_ELEM(xiter_trav->xiter_left)
        if (XRBT_ELEM_LT(
                xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_trav->xiter_left)))
        {
            xiter_trav = xiter_trav->xiter_left;
        }
        else
        {
            // xrbt_elem > XRBT_ITER_ELEM(xiter_trav->xiter_left)
            if (XRBT_ELEM_LT(
                    xrbt_this, XRBT_ITER_ELEM(xiter_trav->xiter_left), xrbt_elem))
            {
                if (XRBT_ITER_ISNIL(xiter_trav->xiter_left->xiter_right))
                {
                    *xrbt_dpos = XDPOS_RIGHT;
                    return xiter_trav->xiter_left;
                }

                return rbtree_dpos_root(
                            xrbt_this,
                            xrbt_elem,
                            xiter_trav->xiter_left->xiter_right,
                            xrbt_dpos);
            }

            // xrbt_elem == XRBT_ITER_ELEM(xiter_trav->xiter_left)
            *xrbt_dpos = XDPOS_NONE;
            return xiter_trav->xiter_left;
        }
    }

    *xrbt_dpos = XDPOS_LEFT;
    return xiter_trav;
#else
    //======================================

    while (XRBT_ITER_NOTNIL(xiter_hint))
    {
        xiter_trav = xiter_hint;

        //======================================
        // the sub branch of left

        while (XRBT_ITER_NOTNIL(xiter_trav->xiter_left))
        {
            if (XRBT_ELEM_LT(
                    xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_trav->xiter_left)))
            {
                xiter_trav = xiter_trav->xiter_left;
            }
            else
            {
                if (XRBT_ELEM_LT(
                        xrbt_this, XRBT_ITER_ELEM(xiter_trav->xiter_left), xrbt_elem))
                {
                    if (XRBT_ITER_ISNIL(xiter_trav->xiter_left->xiter_right))
                    {
                        *xrbt_dpos = XDPOS_RIGHT;
                        return xiter_trav->xiter_left;
                    }

                    return rbtree_dpos_root(
                                xrbt_this,
                                xrbt_elem,
                                xiter_trav->xiter_left->xiter_right,
                                xrbt_dpos);
                }

                // xrbt_elem == XRBT_ITER_ELEM(xiter_trav->xiter_left)
                *xrbt_dpos = XDPOS_NONE;
                return xiter_trav->xiter_left;
            }
        }

        //======================================
        // the precursor of parent

        while (XRBT_ITER_NOTNIL(xiter_hint->xiter_parent) &&
               (xiter_hint->xiter_parent->xiter_left == xiter_hint))
        {
            xiter_hint = xiter_hint->xiter_parent;
        }

        xiter_hint = xiter_hint->xiter_parent;

        // xrbt_elem > XRBT_ITER_ELEM(xiter_hint)
        if (XRBT_ITER_ISNIL(xiter_hint) ||
            XRBT_ELEM_LT(xrbt_this, XRBT_ITER_ELEM(xiter_hint), xrbt_elem))
        {
            *xrbt_dpos = XDPOS_LEFT;
            return xiter_trav;
        }

        // xrbt_elem == XRBT_ITER_ELEM(xiter_hint)
        if (!XRBT_ELEM_LT(xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_hint)))
        {
            *xrbt_dpos = XDPOS_NONE;
            return xiter_hint;
        }

        //======================================
    }

    *xrbt_dpos = XDPOS_NONE;
    return xiter_hint;
#endif
}

/**********************************************************/
/**
 * @brief 
 * 协助 @see rbtree_dpos_hint() 接口，实现树结构体的右侧方向检索操作。
 */
static xrbt_iter_t rbtree_dpos_right(
                        xrbt_this_t xrbt_this,
                        xrbt_elem_t xrbt_elem,
                        xrbt_iter_t xiter_hint,
                        xrbt_dpos_t * xrbt_dpos)
{
    xrbt_iter_t xiter_trav = xiter_hint;
#if 1
    //======================================
    // the precursor of parent

    for (;;)
    {
        xiter_trav = rbtree_successor_parent(xiter_hint);
        if (XRBT_ITER_ISNIL(xiter_trav))
        {
            break;
        }

        // xrbt_elem > XRBT_ITER_ELEM(xiter_trav)
        if (XRBT_ELEM_LT(xrbt_this, XRBT_ITER_ELEM(xiter_trav), xrbt_elem))
        {
            xiter_hint = xiter_trav;
        }
        else
        {
            // xrbt_elem < XRBT_ITER_ELEM(xiter_trav)
            if (XRBT_ELEM_LT(xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_trav)))
            {
                break;
            }

            // xrbt_elem == XRBT_ITER_ELEM(xiter_trav)
            *xrbt_dpos = XDPOS_NONE;
            return xiter_trav;
        }
    }

    //======================================
    // the sub branch of right

    for (xiter_trav = xiter_hint; XRBT_ITER_NOTNIL(xiter_trav->xiter_right); )
    {
        // xrbt_elem > XRBT_ITER_ELEM(xiter_trav->xiter_right)
        if (XRBT_ELEM_LT(
                xrbt_this, XRBT_ITER_ELEM(xiter_trav->xiter_right), xrbt_elem))
        {
            xiter_trav = xiter_trav->xiter_right;
        }
        else
        {
            // xrbt_elem < XRBT_ITER_ELEM(xiter_trav->xiter_right)
            if (XRBT_ELEM_LT(
                    xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_trav->xiter_right)))
            {
                if (XRBT_ITER_ISNIL(xiter_trav->xiter_right->xiter_left))
                {
                    *xrbt_dpos = XDPOS_LEFT;
                    return xiter_trav->xiter_right;
                }

                return rbtree_dpos_root(
                            xrbt_this,
                            xrbt_elem,
                            xiter_trav->xiter_right->xiter_left,
                            xrbt_dpos);
            }

            // xrbt_elem == XRBT_ITER_ELEM(xiter_trav->xiter_right)
            *xrbt_dpos = XDPOS_NONE;
            return xiter_trav->xiter_right;
        }
    }

    *xrbt_dpos = XDPOS_RIGHT;
    return xiter_trav;
#else
    while (XRBT_ITER_NOTNIL(xiter_hint))
    {
        xiter_trav = xiter_hint;

        //======================================
        // the sub branch of right

        while (XRBT_ITER_NOTNIL(xiter_trav->xiter_right))
        {
            if (XRBT_ELEM_LT(
                    xrbt_this, XRBT_ITER_ELEM(xiter_trav->xiter_right), xrbt_elem))
            {
                xiter_trav = xiter_trav->xiter_right;
            }
            else
            {
                if (XRBT_ELEM_LT(
                        xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_trav->xiter_right)))
                {
                    if (XRBT_ITER_ISNIL(xiter_trav->xiter_right->xiter_left))
                    {
                        *xrbt_dpos = XDPOS_LEFT;
                        return xiter_trav->xiter_right;
                    }

                    return rbtree_dpos_root(
                                xrbt_this,
                                xrbt_elem,
                                xiter_trav->xiter_right->xiter_left,
                                xrbt_dpos);
                }

                // xrbt_elem == XRBT_ITER_ELEM(xiter_trav->xiter_right)
                *xrbt_dpos = XDPOS_NONE;
                return xiter_trav->xiter_right;
            }
        }

        //======================================
        // the successor of parent

        while (XRBT_ITER_NOTNIL(xiter_hint->xiter_parent) &&
               (xiter_hint->xiter_parent->xiter_right == xiter_hint))
        {
            xiter_hint = xiter_hint->xiter_parent;
        }

        xiter_hint = xiter_hint->xiter_parent;

        // xrbt_elem < XRBT_ITER_ELEM(xiter_hint)
        if (XRBT_ITER_ISNIL(xiter_hint) ||
            XRBT_ELEM_LT(xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_hint)))
        {
            *xrbt_dpos = XDPOS_RIGHT;
            return xiter_trav;
        }

        // xrbt_elem == XRBT_ITER_ELEM(xiter_hint)
        if (!XRBT_ELEM_LT(xrbt_this, XRBT_ITER_ELEM(xiter_hint), xrbt_elem))
        {
            *xrbt_dpos = XDPOS_NONE;
            return xiter_hint;
        }

        //======================================
    }

    *xrbt_dpos = XDPOS_NONE;
    return xiter_hint;
#endif
}

/**********************************************************/
/**
 * @brief 
 * 在给予检索遍历操作的起始迭代器位置的情况下，获取节点元素值可停靠的位置。
 * 
 * @param [in ] xrbt_this  : xstd_rbtree_t 对象。
 * @param [in ] xrbt_elem  : 节点元素值。
 * @param [in ] xiter_hint : 检索遍历操作的起始迭代器位置。
 * @param [out] xrbt_dpos  : 返回的停靠方式（参看 xrbt_dpos_t 枚举值）。
 * 
 * @return xrbt_iter_t : 可停靠节点位置的迭代器。
 * 若返回的 xrbt_dpos == XDPOS_NONE 时，
 * 迭代器对应的 节点元素值 与 xrbt_elem 相等。
 */
static xrbt_iter_t rbtree_dpos_hint(
                        xrbt_this_t xrbt_this,
                        xrbt_elem_t xrbt_elem,
                        xrbt_iter_t xiter_hint,
                        xrbt_dpos_t * xrbt_dpos)
{
    if (XRBT_ITER_ISNIL(xiter_hint))
    {
        return rbtree_dpos_root(
                        xrbt_this,
                        xrbt_elem,
                        xrbt_this->xiter_root,
                        xrbt_dpos);
    }

    // xrbt_elem > XRBT_ITER_ELEM(xiter_hint)
    if (XRBT_ELEM_LT(xrbt_this, XRBT_ITER_ELEM(xiter_hint), xrbt_elem))
    {
        return rbtree_dpos_right(xrbt_this, xrbt_elem, xiter_hint, xrbt_dpos);
    }

    // xrbt_elem < XRBT_ITER_ELEM(xiter_hint)
    if (XRBT_ELEM_LT(xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_hint)))
    {
        return rbtree_dpos_left(xrbt_this, xrbt_elem, xiter_hint, xrbt_dpos);
    }

    // xrbt_elem == XRBT_ITER_ELEM(xiter_hint)
    *xrbt_dpos = XDPOS_NONE;
    return xiter_hint;
}

/**********************************************************/
/**
 * @brief 向 xstd_rbtree_t 对象插入已构建的节点。
 * 
 * @param [in,out] xrbt_this  : xstd_rbtree_t 对象。
 * @param [in    ] xiter_node : 迭代器节点。
 * @param [in    ] xiter_dock : 停靠 xiter_node 节点的位置（父级节点）。
 * @param [in    ] xdpos_pick : 停靠方式。
 * 
 * @return xrbt_iter_t : 返回所对应的迭代器节点。
 */
static xrbt_iter_t rbtree_insert_node(
                        xrbt_this_t xrbt_this,
                        xrbt_iter_t xiter_node,
                        xrbt_iter_t xiter_dock,
                        xrbt_dpos_t xdpos_pick)
{
    //======================================

    xiter_node->xiter_parent = xiter_dock;
    if (XRBT_ITER_ISNIL(xiter_dock))
    {
        xrbt_this->xiter_root  = xiter_node;
        xrbt_this->xiter_lnode = xiter_node;
        xrbt_this->xiter_rnode = xiter_node;
    }
    else if (XDPOS_LEFT == xdpos_pick)
    {
        xiter_dock->xiter_left = xiter_node;

        if (xiter_dock == xrbt_this->xiter_lnode)
        {
            xrbt_this->xiter_lnode = xiter_node;
        }
    }
    else // (XDPOS_RIGHT == xdpos_pick)
    {
        xiter_dock->xiter_right = xiter_node;

        if (xiter_dock == xrbt_this->xiter_rnode)
        {
            xrbt_this->xiter_rnode = xiter_node;
        }
    }

    xiter_node->xst_color   = XCLR_RED;
    xiter_node->xst_ksize   = XRBT_ESIZE(xrbt_this);
    xiter_node->xiter_left  = XRBT_ITER_NIL(xrbt_this);
    xiter_node->xiter_right = XRBT_ITER_NIL(xrbt_this);

#if (XSTD_DEBUG_LEVEL >= XSTD_DEBUG_LOWER)
    xiter_node->xrbt_owner  = xrbt_this;
#endif // XSTD_DEBUG_LOWER

    //======================================

    rbtree_dock_fixup(xrbt_this, xiter_node);
    xrbt_this->xrbt_csize += 1;

    //======================================

    return xiter_node;
}

/**********************************************************/
/**
 * @brief 向 xstd_rbtree_t 对象插入新节点。
 * 
 * @param [in,out] xrbt_this  : xstd_rbtree_t 对象。
 * @param [in    ] xrbt_elem  : 新节点的元素值。
 * @param [in    ] xfunc_dpos : 查找可停靠节点的操作函数。
 * @param [in    ] xiter_hint : 查找可停靠节点的起始节点。
 * 
 * @param [out   ] xbt_clash  : 
 * 检测所插入的 新节点元素值 是否与 xstd_rbtree_t 对象
 * 中原有的 节点元素值 是否冲突。
 * 
 * @return xrbt_iter_t : 返回节点元素对应的 迭代器。
 */
static xrbt_iter_t rbtree_insert_from(
                        xrbt_this_t xrbt_this,
                        xrbt_elem_t xrbt_elem,
                        xrbt_fdpos_t xfunc_dpos,
                        xrbt_iter_t xiter_hint,
                        xrbt_bool_t * xbt_clash)
{
    xrbt_iter_t xiter_node = XRBT_ITER_NIL(xrbt_this);
    xrbt_dpos_t xdpos_pick = XDPOS_NONE;
    xrbt_iter_t xiter_dock = xfunc_dpos(
                                    xrbt_this,
                                    xrbt_elem,
                                    xiter_hint,
                                    &xdpos_pick);
    if (XDPOS_NONE == xdpos_pick)
    {
        if (XRBT_NULL != xbt_clash)
            *xbt_clash = XRBT_TRUE;
        return xiter_dock;
    }

    if (XRBT_NULL != xbt_clash)
        *xbt_clash = XRBT_FALSE;
    xiter_node = rbtree_node_malloc(xrbt_this);

    XRBT_ALFROM(xrbt_this, XRBT_ITER_ELEM(xiter_node), xrbt_elem);

    return rbtree_insert_node(xrbt_this, xiter_node, xiter_dock, xdpos_pick);
}

/**********************************************************/
/**
 * @brief 向 xstd_rbtree_t 对象插入新节点（使用右值 move 操作进行元素拷贝）。
 * 
 * @param [in,out] xrbt_this  : xstd_rbtree_t 对象。
 * @param [in    ] xrbt_elem  : 新节点的元素值。
 * @param [in    ] xfunc_dpos : 查找可停靠节点的操作函数。
 * @param [in    ] xiter_hint : 查找可停靠节点的起始节点。
 * 
 * @param [out   ] xbt_clash  : 
 * 检测所插入的 新节点元素值 是否与 xstd_rbtree_t 对象
 * 中原有的 节点元素值 是否冲突。
 * 
 * @return xrbt_iter_t : 返回节点元素对应的 迭代器。
 */
static xrbt_iter_t rbtree_insert_move(
                        xrbt_this_t xrbt_this,
                        xrbt_elem_t xrbt_elem,
                        xrbt_fdpos_t xfunc_dpos,
                        xrbt_iter_t xiter_hint,
                        xrbt_bool_t * xbt_clash)
{
    xrbt_iter_t xiter_node = XRBT_ITER_NIL(xrbt_this);
    xrbt_dpos_t xdpos_pick = XDPOS_NONE;
    xrbt_iter_t xiter_dock = xfunc_dpos(
                                    xrbt_this,
                                    xrbt_elem,
                                    xiter_hint,
                                    &xdpos_pick);
    if (XDPOS_NONE == xdpos_pick)
    {
        if (XRBT_NULL != xbt_clash)
            *xbt_clash = XRBT_TRUE;
        return xiter_dock;
    }

    if (XRBT_NULL != xbt_clash)
        *xbt_clash = XRBT_FALSE;
    xiter_node = rbtree_node_malloc(xrbt_this);

    XRBT_ALMOVE(xrbt_this, XRBT_ITER_ELEM(xiter_node), xrbt_elem);

    return rbtree_insert_node(xrbt_this, xiter_node, xiter_dock, xdpos_pick);
}

//====================================================================

// 
// xstd_rbtree_t 的外部操作接口
// 

/**********************************************************/
/**
 * @brief 返回内部的 sizeof(xstd_rbtree_t) 值。
 */
xrbt_size_t std_rbtree_sizeof(void)
{
    return (xrbt_size_t)sizeof(xstd_rbtree_t);
}

/**********************************************************/
/**
 * @brief 创建 xstd_rbtree_t 对象。
 * @note
 * 1. xfunc_initial 与 xfunc_release 在实现流程中应起到资源 初始化/释放 的对应关系。
 * 2. 请使用 @see std_rbtree_destroy() 销毁返回的对象。
 * 
 * @param [in ] xrbt_ctxt  : 红黑树所存储节点元素值的类型上下文描述信息。
 * @param [in ] xfunc_kcmp : 比较 节点元素 的回调函数（为 XRBT_NULL 时，取内部默认函数）。
 * 
 * @return xrbt_this_t : 
 * xstd_rbtree_t 对象指针；若 返回 XRBT_NULL，则表示创建失败。
 */
xrbt_this_t std_rbtree_create(
                xrbt_ctxt_t xrbt_ctxt,
                xrbt_kcmpfunc_t xfunc_kcmp)
{
    XASSERT(0 != xrbt_ctxt);
    XASSERT(xrbt_ctxt->xstd_etype != 0);
    XASSERT(xrbt_ctxt->xstd_esize != 0);
    XASSERT(xrbt_ctxt->xstd_esize <= XRBT_MAX_ESIZE);

    xstd_altor_t xstd_altor = XSTD_ALTOR_NCREF(xrbt_ctxt->xstd_altor);
    xrbt_this_t xrbt_this = 
        (xrbt_this_t)xstd_altor->xfunc_allocate(sizeof(xstd_rbtree_t));
    XASSERT(XRBT_NULL != xrbt_this);

    return std_rbtree_emplace_create(xrbt_this, xrbt_ctxt, xfunc_kcmp);
}

/**********************************************************/
/**
 * @brief 销毁 xstd_rbtree_t 对象，其由 @see std_rbtree_create() 所创建。
 */
xrbt_void_t std_rbtree_destroy(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);

    xstd_altor_t xstd_altor = XRBT_ALTOR(xrbt_this);

    std_rbtree_emplace_destroy(xrbt_this);
    xstd_altor->xfunc_dealloc(xrbt_this);
}

/**********************************************************/
/**
 * @brief 在已开辟 xstd_rbtree_t 对象缓存的位置上创建 xstd_rbtree_t 对象。
 * @note
 * 1. xrbt_this 的缓存大小必须大于等于 sizeof(xstd_rbtree_t) 值。
 * 2. xrbt_this 对象销毁时，请使用 @see std_rbtree_emplace_destroy() 。
 * 3. 其他参数请参看 @see std_rbtree_create() 对应的参数说明。
 */
xrbt_this_t std_rbtree_emplace_create(
                xrbt_this_t xrbt_this,
                xrbt_ctxt_t xrbt_ctxt,
                xrbt_kcmpfunc_t xfunc_kcmp)
{
    XASSERT(0 != xrbt_ctxt);
    XASSERT(xrbt_ctxt->xstd_etype != 0);
    XASSERT(xrbt_ctxt->xstd_esize != 0);
    XASSERT(xrbt_ctxt->xstd_esize <= XRBT_MAX_ESIZE);

    //======================================

    XRBT_ECTXT_UPDATE(xrbt_this, xrbt_ctxt);

    XRBT_RESET_NIL(xrbt_this);

    xrbt_this->xfunc_kcmp  = (XRBT_NULL != xfunc_kcmp) ? xfunc_kcmp : xstd_fcmp_comm.xfunc_lt;
    xrbt_this->xrbt_csize  = 0;
    xrbt_this->xiter_root  = XRBT_ITER_NIL(xrbt_this);
    xrbt_this->xiter_lnode = XRBT_ITER_NIL(xrbt_this);
    xrbt_this->xiter_rnode = XRBT_ITER_NIL(xrbt_this);

    //======================================

    return xrbt_this;
}

/**********************************************************/
/**
 * @brief
 * 在已开辟 xstd_rbtree_t 对象缓存的位置上销毁 xstd_rbtree_t 对象，
 * 其由 @see std_rbtree_emplace_create() 所创建。
 */
xrbt_void_t std_rbtree_emplace_destroy(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    std_rbtree_clear(xrbt_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的 上下文信息。
 */
xrbt_ctxt_t std_rbtree_ctxt(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    return XRBT_ECTXT(xrbt_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的类型标识。
 */
xrbt_size_t std_rbtree_etype(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    return XRBT_ETYPE(xrbt_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象中的节点数量。
 */
xrbt_size_t std_rbtree_size(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    return xrbt_this->xrbt_csize;
}

/**********************************************************/
/**
 * @brief 判断 xstd_rbtree_t 对象中节点数量是否为空。
 */
xrbt_bool_t std_rbtree_empty(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    return (0 == xrbt_this->xrbt_csize);
}

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象可容纳最大节点数量。
 */
xrbt_size_t std_rbtree_maxsize(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    return XRBT_MAX_SIZE(xrbt_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象中的左手臂长度。
 */
xrbt_size_t std_rbtree_left_length(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);

    xrbt_size_t xst_length = 0;
    xrbt_iter_t xiter_node = XRBT_ITER_BEGIN(xrbt_this);

    while (xiter_node != xrbt_this->xiter_root)
    {
        xst_length += 1;
        xiter_node = xiter_node->xiter_parent;
    }

    return xst_length;
}

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象中的右手臂长度。
 */
xrbt_size_t std_rbtree_right_length(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);

    xrbt_size_t xst_length = 0;
    xrbt_iter_t xiter_node = XRBT_ITER_RBEGIN(xrbt_this);

    while (xiter_node != xrbt_this->xiter_root)
    {
        xst_length += 1;
        xiter_node = xiter_node->xiter_parent;
    }

    return xst_length;
}

/**********************************************************/
/**
 * @brief 清除 xstd_rbtree_t 对象中的所有节点。
 */
xrbt_void_t std_rbtree_clear(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    rbtree_clear_branch(xrbt_this, xrbt_this->xiter_root);

    XRBT_RESET_NIL(xrbt_this);

    xrbt_this->xrbt_csize  = 0;
    xrbt_this->xiter_root  = XRBT_ITER_NIL(xrbt_this);
    xrbt_this->xiter_lnode = XRBT_ITER_NIL(xrbt_this);
    xrbt_this->xiter_rnode = XRBT_ITER_NIL(xrbt_this);
}

/**********************************************************/
/**
 * @brief 向 xstd_rbtree_t 对象插入新节点。
 * 
 * @param [in,out] xrbt_this : xstd_rbtree_t 对象。
 * @param [in    ] xrbt_elem : 新节点的元素值。
 * 
 * @param [out   ] xbt_clash : 
 * 检测所插入的 新节点元素值 是否与 xstd_rbtree_t 对象中
 * 原有的 节点元素值 是否冲突。
 * 入参不为 XRBT_NULL 时，
 *  若返回值为 XRBT_TRUE，表示产生冲突，插入操作算是失败的；
 *  否则，返回 XRBT_FALSE，表示产生冲突，插入操作
 *  算是（新增节点）成功的。
 * 入参为 XRBT_NULL 时，则忽略该检测操作。
 * 
 * @return xrbt_iter_t : 返回 节点元素 对应的 迭代器。
 */
xrbt_iter_t std_rbtree_insert(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem,
                    xrbt_bool_t * xbt_clash)
{
    XASSERT(XRBT_NULL != xrbt_this);
    XASSERT(XRBT_NULL != xrbt_elem);
    XASSERT(xrbt_this->xrbt_csize < XRBT_MAX_SIZE(xrbt_this));

    return rbtree_insert_from(
                    xrbt_this,
                    xrbt_elem,
                    &rbtree_dpos_root,
                    xrbt_this->xiter_root,
                    xbt_clash);
}

/**********************************************************/
/**
 * @brief 向 xstd_rbtree_t 对象安放新节点。
 * 
 * @param [in,out] xrbt_this : xstd_rbtree_t 对象。
 * 
 * @param [in    ] xrbt_elem : 
 * 新节点的元素值（使用 右值move 操作进行存储）。
 * 
 * @param [out   ] xbt_clash : 
 * 检测所插入的 新节点元素值 是否与 xstd_rbtree_t 对象中
 * 原有的 节点元素值 是否冲突。
 * 入参不为 XRBT_NULL 时，
 *  若返回值为 XRBT_TRUE，表示产生冲突，安放操作算是失败的；
 *  否则，返回 XRBT_FALSE，表示产生冲突，安放操作
 *  算是（新增节点）成功的。
 * 入参为 XRBT_NULL 时，则忽略该检测操作。
 * 
 * @return xrbt_iter_t : 返回 节点元素 对应的 迭代器。
 */
xrbt_iter_t std_rbtree_emplace(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem,
                    xrbt_bool_t * xbt_clash)
{
    XASSERT(XRBT_NULL != xrbt_this);
    XASSERT(XRBT_NULL != xrbt_elem);
    XASSERT(xrbt_this->xrbt_csize < XRBT_MAX_SIZE(xrbt_this));

    return rbtree_insert_move(
                    xrbt_this,
                    xrbt_elem,
                    &rbtree_dpos_root,
                    xrbt_this->xiter_root,
                    xbt_clash);
}

/**********************************************************/
/**
 * @brief 
 * 在给出初始检索的节点位置的情况下，
 * 向 xstd_rbtree_t 对象插入新节点。
 * 
 * @param [in,out] xrbt_this  : xstd_rbtree_t 对象。
 * @param [in    ] xrbt_elem  : 新节点的元素值。
 * @param [in    ] xiter_hint : 给出初始检索的节点位置。
 * 
 * @param [out   ] xbt_clash  : 
 * 检测所插入的 新节点元素值 是否与 xstd_rbtree_t 对象中
 * 原有的 节点元素值 是否冲突。
 * 入参不为 XRBT_NULL 时，
 *  若返回值为 XRBT_TRUE，表示产生冲突，插入操作算是失败的；
 *  否则，返回 XRBT_FALSE，表示产生冲突，插入操作
 *  算是（新增节点）成功的。
 * 入参为 XRBT_NULL 时，则忽略该检测操作。
 * 
 * @return xrbt_iter_t : 返回 节点元素 对应的 迭代器。
 */
xrbt_iter_t std_rbtree_insert_hint(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem,
                    xrbt_iter_t xiter_hint,
                    xrbt_bool_t * xbt_clash)
{
    XASSERT(XRBT_NULL != xrbt_this);
    XASSERT(XRBT_NULL != xrbt_elem);
    XASSERT(xrbt_this->xrbt_csize < XRBT_MAX_SIZE(xrbt_this));
    XASSERT(XRBT_NULL != xiter_hint);
    XASSERT(XRBT_ITER_ISDOCKED(xiter_hint));
    XASSERT(xrbt_this == xiter_hint->xrbt_owner);

    return rbtree_insert_from(
                    xrbt_this,
                    xrbt_elem,
                    &rbtree_dpos_hint,
                    xiter_hint,
                    xbt_clash);
}

/**********************************************************/
/**
 * @brief 
 * 在给出初始检索的节点位置的情况下，
 * 向 xstd_rbtree_t 对象安放新节点。
 * 
 * @param [in,out] xrbt_this  : xstd_rbtree_t 对象。
 * 
 * @param [in    ] xrbt_elem  : 
 * 新节点的元素值（使用 右值move 操作进行存储）。
 * 
 * @param [in    ] xiter_hint : 给出初始检索的节点位置。
 * 
 * @param [out   ] xbt_clash  : 
 * 检测所插入的 新节点元素值 是否与 xstd_rbtree_t 对象中
 * 原有的 节点元素值 是否冲突。
 * 入参不为 XRBT_NULL 时，
 *  若返回值为 XRBT_TRUE，表示产生冲突，插入操作算是失败的；
 *  否则，返回 XRBT_FALSE，表示产生冲突，插入操作
 *  算是（新增节点）成功的。
 * 入参为 XRBT_NULL 时，则忽略该检测操作。
 * 
 * @return xrbt_iter_t : 返回 节点元素 对应的 迭代器。
 */
xrbt_iter_t std_rbtree_emplace_hint(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem,
                    xrbt_iter_t xiter_hint,
                    xrbt_bool_t * xbt_clash)
{
    XASSERT(XRBT_NULL != xrbt_this);
    XASSERT(XRBT_NULL != xrbt_elem);
    XASSERT(xrbt_this->xrbt_csize < XRBT_MAX_SIZE(xrbt_this));
    XASSERT(XRBT_NULL != xiter_hint);
    XASSERT(XRBT_ITER_ISDOCKED(xiter_hint));
    XASSERT(xrbt_this == xiter_hint->xrbt_owner);

    return rbtree_insert_move(
                    xrbt_this,
                    xrbt_elem,
                    &rbtree_dpos_hint,
                    xiter_hint,
                    xbt_clash);
}

/**********************************************************/
/**
 * @brief 从 xstd_rbtree_t 对象中删除指定节点。
 */
xrbt_void_t std_rbtree_erase(xrbt_this_t xrbt_this, xrbt_iter_t xiter_node)
{
    XASSERT(XRBT_NULL != xrbt_this);
    XASSERT(XRBT_NULL != xiter_node);
    XASSERT(XRBT_ITER_NOTNIL(xiter_node) && XRBT_ITER_ISDOCKED(xiter_node));
    XASSERT(xrbt_this == xiter_node->xrbt_owner);

    rbtree_node_dealloc(xrbt_this, std_rbtree_undock(xrbt_this, xiter_node));
}

/**********************************************************/
/**
 * @brief 从 xstd_rbtree_t 对象中删除指定元素值的节点。
 * 
 * @return xrbt_bool_t : 操作是否成功。
 * 返回 XRBT_FALSE 时，表示 指定的元素值，
 * 未存储于 xstd_rbtree_t 对象中。
 */
xrbt_bool_t std_rbtree_erase_elem(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem)
{
    XASSERT(XRBT_NULL != xrbt_this);
    XASSERT(XRBT_NULL != xrbt_elem);

    xrbt_iter_t xiter_node = std_rbtree_find(xrbt_this, xrbt_elem);
    if (XRBT_ITER_ISNIL(xiter_node))
    {
        return XRBT_FALSE;
    }

    std_rbtree_erase(xrbt_this, xiter_node);

    return XRBT_TRUE;
}

/**********************************************************/
/**
 * @brief 将节点对象停靠（插入）到 xstd_rbtree_t 中。
 * @note
 * xiter_node 必须处于分离状态（参看 @see std_rbtree_undocked()），
 * 而且其节点元素类型必须 与 xrbt_this 存储的节点类型相同。
 * 
 * @param [in,out] xrbt_this  : xstd_rbtree_t 对象。
 * @param [in    ] xiter_node : 停靠操作的节点对象。
 * 
 * @return xrbt_iter_t : 节点对象。
 * - 返回的 节点对象 == xiter_node，停靠成功。
 * - 返回的 节点对象 != xiter_node，停靠失败（节点元素值冲突）。
 */
xrbt_iter_t std_rbtree_dock(xrbt_this_t xrbt_this, xrbt_iter_t xiter_node)
{
    XASSERT(XRBT_NULL != xrbt_this);
    XASSERT(XRBT_NULL != xiter_node);
    XASSERT(XRBT_ITER_NOTNIL(xiter_node) && XRBT_ITER_ISUNDOCKED(xiter_node));
    XASSERT(XRBT_ISSAME_TYPE(xrbt_this, xiter_node->xrbt_owner));
    XASSERT(xrbt_this->xrbt_csize < XRBT_MAX_SIZE(xrbt_this));

    xrbt_dpos_t xdpos_pick = XDPOS_NONE;
    xrbt_iter_t xiter_dock = rbtree_dpos_root(
                                    xrbt_this,
                                    XRBT_ITER_ELEM(xiter_node),
                                    xrbt_this->xiter_root,
                                    &xdpos_pick);

    if (XDPOS_NONE == xdpos_pick)
    {
        return xiter_dock;
    }

    return rbtree_insert_node(xrbt_this, xiter_node, xiter_dock, xdpos_pick);
}

/**********************************************************/
/**
 * @brief 将节点对象从 xstd_rbtree_t 中分离（移除）出来。
 * @note  xiter_node 当前必须隶属于 xrbt_this 。
 * 
 * @param [in,out] xrbt_this  : xstd_rbtree_t 对象。
 * @param [in    ] xiter_node : 分离操作的节点对象。
 * 
 * @return xrbt_iter_t : 返回的 节点对象 == xiter_node。
 */
xrbt_iter_t std_rbtree_undock(xrbt_this_t xrbt_this, xrbt_iter_t xiter_node)
{
    XASSERT(XRBT_NULL != xrbt_this);
    XASSERT((XRBT_NULL != xiter_node) && XRBT_ITER_NOTNIL(xiter_node));
    XASSERT(xrbt_this == xiter_node->xrbt_owner);

    xrbt_iter_t xiter_fixup  = XRBT_ITER_NIL(xrbt_this);
    xrbt_iter_t xiter_parent = XRBT_ITER_NIL(xrbt_this);
    xrbt_iter_t xiter_where  = xiter_node;
    xrbt_iter_t xiter_ntrav  = xiter_where;

    if (XRBT_ITER_ISNIL(xiter_ntrav->xiter_left))
    {
        xiter_fixup = xiter_ntrav->xiter_right;
    }
    else if (XRBT_ITER_ISNIL(xiter_ntrav->xiter_right))
    {
        xiter_fixup = xiter_ntrav->xiter_left;
    }
    else
    {
        xiter_ntrav = rbtree_successor(xiter_node);
        xiter_fixup = xiter_ntrav->xiter_right;
    }

    if (xiter_ntrav == xiter_where)
    {
        xiter_parent = xiter_where->xiter_parent;
        if (XRBT_ITER_NOTNIL(xiter_fixup))
            xiter_fixup->xiter_parent = xiter_parent;

        if (xrbt_this->xiter_root == xiter_where)
        {
            xrbt_this->xiter_root = xiter_fixup;
        }
        else if (xiter_parent->xiter_left == xiter_where)
        {
            xiter_parent->xiter_left = xiter_fixup;
        }
        else
        {
            xiter_parent->xiter_right = xiter_fixup;
        }

        if (xrbt_this->xiter_lnode == xiter_where)
        {
            xrbt_this->xiter_lnode =
                XRBT_ITER_ISNIL(xiter_fixup) ?
                    xiter_parent : rbtree_far_left(xiter_fixup);
        }

        if (xrbt_this->xiter_rnode == xiter_where)
        {
            xrbt_this->xiter_rnode =
                XRBT_ITER_ISNIL(xiter_fixup) ?
                    xiter_parent : rbtree_far_right(xiter_fixup);
        }
    }
    else
    {
        xiter_where->xiter_left->xiter_parent = xiter_ntrav;
        xiter_ntrav->xiter_left = xiter_where->xiter_left;

        if (xiter_ntrav == xiter_where->xiter_right)
        {
            xiter_parent = xiter_ntrav;
        }
        else
        {
            xiter_parent = xiter_ntrav->xiter_parent;
            if (XRBT_ITER_NOTNIL(xiter_fixup))
            {
                xiter_fixup->xiter_parent = xiter_parent;
            }

            xiter_parent->xiter_left = xiter_fixup;
            xiter_ntrav->xiter_right = xiter_where->xiter_right;
            xiter_where->xiter_right->xiter_parent = xiter_ntrav;
        }

        if (xrbt_this->xiter_root == xiter_where)
        {
            xrbt_this->xiter_root = xiter_ntrav;
        }
        else if (xiter_where->xiter_parent->xiter_left == xiter_where)
        {
            xiter_where->xiter_parent->xiter_left = xiter_ntrav;
        }
        else
        {
            xiter_where->xiter_parent->xiter_right = xiter_ntrav;
        }

        xiter_ntrav->xiter_parent = xiter_where->xiter_parent;

        // recolor it (swap color)
        if (xiter_ntrav->xst_color != xiter_where->xst_color)
        {
            XRBT_ITER_SWCLR(xiter_ntrav);
            XRBT_ITER_SWCLR(xiter_where);
        }
    }

    if (XCLR_BLACK == xiter_where->xst_color)
    {
        rbtree_undock_fixup(xrbt_this, xiter_fixup, xiter_parent);
    }

    XRBT_ITER_UNDOCK(xiter_where);

    XASSERT(xrbt_this->xrbt_csize > 0);
    xrbt_this->xrbt_csize -= 1;

    return xiter_where;
}

/**********************************************************/
/**
 * @brief 将 xrbt_other 对象中的节点转移到 xrbt_this 对象中。
 * @note 
 * 1. xrbt_other 与 xrbt_this 的节点存储类型必须一致。
 * 2. xrbt_other 与 xrbt_this 的节点，可能有相同值的节点，
 *    这部分节点不会被转移，完成操作后，依然会保留在 xrbt_other 中。
 * 
 * @param [in,out] xrbt_this  : 转移至的目标 红黑树对象。
 * @param [in,out] xrbt_other : 被转移的源 红黑树对象。
 */
xrbt_void_t std_rbtree_merge(xrbt_this_t xrbt_this, xrbt_this_t xrbt_other)
{
    XASSERT(XRBT_NULL != xrbt_this);
    XASSERT(XRBT_NULL != xrbt_other);
    XASSERT(XRBT_ISSAME_TYPE(xrbt_this, xrbt_other));

    xrbt_dpos_t xdpos_pick = XDPOS_NONE;
    xrbt_iter_t xiter_hint = xrbt_this->xiter_root;
    xrbt_iter_t xiter_node = XRBT_ITER_NIL(xrbt_this);

    xrbt_iter_t xiter_trav = XRBT_ITER_BEGIN(xrbt_other);

    while (xiter_trav != XRBT_ITER_END(xrbt_other))
    {
        xiter_hint = rbtree_dpos_hint(
                            xrbt_this,
                            XRBT_ITER_ELEM(xiter_trav),
                            xiter_hint,
                            &xdpos_pick);

        if (XDPOS_NONE == xdpos_pick)
        {
            xiter_trav = rbtree_successor(xiter_trav);
            continue;
        }

        xiter_node = xiter_trav;
        xiter_trav = rbtree_successor(xiter_trav);

        std_rbtree_undock(xrbt_other, xiter_node);
        xiter_hint = rbtree_insert_node(
                            xrbt_this,
                            xiter_node,
                            xiter_hint,
                            xdpos_pick);
    }
}

/**********************************************************/
/**
 * @brief 在 xstd_rbtree_t 对象中查找指定节点。
 * @note  若返回 NIL 则表示 xstd_rbtree_t 对象不包含该节点元素值。
 */
xrbt_iter_t std_rbtree_find(xrbt_this_t xrbt_this, xrbt_elem_t xrbt_elem)
{
    XASSERT((XRBT_NULL != xrbt_this) && (XRBT_NULL != xrbt_elem));

    xrbt_iter_t xiter_node = std_rbtree_lower_bound(xrbt_this, xrbt_elem);

    if (XRBT_ITER_ISNIL(xiter_node) ||
        XRBT_ELEM_LT(xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_node)))
    {
        return XRBT_ITER_NIL(xrbt_this);
    }

    return xiter_node;
}

/**********************************************************/
/**
 * @brief 返回的是首个不小于 指定节点元素值 的 节点位置。
 */
xrbt_iter_t std_rbtree_lower_bound(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem)
{
    XASSERT((XRBT_NULL != xrbt_this) && (XRBT_NULL != xrbt_elem));

    xrbt_iter_t xiter_node = XRBT_ITER_NIL(xrbt_this);
    xrbt_iter_t xiter_trav = xrbt_this->xiter_root;

    while (XRBT_ITER_NOTNIL(xiter_trav))
    {
        if (XRBT_ELEM_LT(xrbt_this, XRBT_ITER_ELEM(xiter_trav), xrbt_elem))
        {
            xiter_trav = xiter_trav->xiter_right;
        }
        else
        {
            xiter_node = xiter_trav;
            xiter_trav = xiter_trav->xiter_left;
        }
    }

    return xiter_node;
}

/**********************************************************/
/**
 * @brief 返回的是首个大于 指定节点元素值 的 节点位置。
 */
xrbt_iter_t std_rbtree_upper_bound(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem)
{
    XASSERT((XRBT_NULL != xrbt_this) && (XRBT_NULL != xrbt_elem));

    xrbt_iter_t xiter_node = XRBT_ITER_NIL(xrbt_this);
    xrbt_iter_t xiter_trav = xrbt_this->xiter_root;

    while (XRBT_ITER_NOTNIL(xiter_trav))
    {
        if (XRBT_ELEM_LT(xrbt_this, xrbt_elem, XRBT_ITER_ELEM(xiter_trav)))
        {
            xiter_node = xiter_trav;
            xiter_trav = xiter_trav->xiter_left;
        }
        else
        {
            xiter_trav = xiter_trav->xiter_right;
        }
    }

    return xiter_node;
}

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的根节点。
 */
xrbt_iter_t std_rbtree_root(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    return xrbt_this->xiter_root;
}

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的正向遍历操作的起始节点。
 */
xrbt_iter_t std_rbtree_begin(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    return XRBT_ITER_BEGIN(xrbt_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的正向遍历操作的终止节点。
 */
xrbt_iter_t std_rbtree_end(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    return XRBT_ITER_END(xrbt_this);
}

/**********************************************************/
/**
 * @brief 返回（正向）下一个节点迭代器。
 */
xrbt_iter_t std_rbtree_next(xrbt_iter_t xiter_node)
{
    XASSERT(XRBT_NULL != xiter_node);
    XASSERT(XRBT_ITER_NOTNIL(xiter_node));
    XASSERT(XRBT_ITER_ISDOCKED(xiter_node));
    return rbtree_successor(xiter_node);
}

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的反向遍历操作的起始节点。
 */
xrbt_iter_t std_rbtree_rbegin(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    return XRBT_ITER_RBEGIN(xrbt_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的反向遍历操作的终止节点。
 */
xrbt_iter_t std_rbtree_rend(xrbt_this_t xrbt_this)
{
    XASSERT(XRBT_NULL != xrbt_this);
    return XRBT_ITER_REND(xrbt_this);
}

/**********************************************************/
/**
 * @brief 返回（反向的）下一个节点迭代器。
 */
xrbt_iter_t std_rbtree_rnext(xrbt_iter_t xiter_node)
{
    XASSERT(XRBT_NULL != xiter_node);
    XASSERT(XRBT_ITER_NOTNIL(xiter_node));
    XASSERT(XRBT_ITER_ISDOCKED(xiter_node));
    return rbtree_precursor(xiter_node);
}

/**********************************************************/
/**
 * @brief 返回 迭代器 对应存储的节点元素。
 */
xrbt_elem_t std_rbtree_elem(xrbt_iter_t xiter_node)
{
    XASSERT(XRBT_NULL != xiter_node);
    XASSERT(XRBT_ITER_NOTNIL(xiter_node));
    return XRBT_ITER_ELEM(xiter_node);
}

/**********************************************************/
/**
 * @brief 判断 节点对象 是否为 NIL 。
 */
xrbt_bool_t std_rbtree_isnil(xrbt_iter_t xiter_node)
{
    XASSERT(XRBT_NULL != xiter_node);
    return XRBT_ITER_ISNIL(xiter_node);
}

/**********************************************************/
/**
 * @brief 判断 节点对象 是否为 非停靠状态（即其已被分离出 xstd_rbtree_t）。
 */
xrbt_bool_t std_rbtree_undocked(xrbt_iter_t xiter_node)
{
    XASSERT((XRBT_NULL != xiter_node) && XRBT_ITER_NOTNIL(xiter_node));
    return XRBT_ITER_ISUNDOCKED(xiter_node);
}

/**********************************************************/
/**
 * @brief 返回 节点对象 所隶属的 xstd_rbtree_t 。
 * @note 
 * 1. xiter_node 迭代器必须处于 停靠状态。
 * 2. 内部会进行节点遍历操作，使用时应注重效率问题。
 */
xrbt_this_t std_rbtree_owner(xrbt_iter_t xiter_node)
{
    XASSERT(XRBT_NULL != xiter_node);
    XASSERT(XRBT_ITER_NOTNIL(xiter_node));
    XASSERT(XRBT_ITER_ISDOCKED(xiter_node));

    while (XRBT_ITER_NOTNIL(xiter_node))
    {
        if (XRBT_ITER_ISNIL(xiter_node->xiter_parent))
        {
            xiter_node = xiter_node->xiter_parent;
            break;
        }

        if (XRBT_ITER_ISNIL(xiter_node->xiter_right))
        {
            xiter_node = xiter_node->xiter_right;
            break;
        }

        xiter_node = xiter_node->xiter_left;
    }

    return ((xrbt_nil_t *)xiter_node)->xrbt_owner;
}

////////////////////////////////////////////////////////////////////////////////

#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif // __GNUC__

////////////////////////////////////////////////////////////////////////////////
